package com.eatme.core.sort;

import com.eatme.core.array.ArrayGenerator;

import java.util.Arrays;
import java.util.Random;

/**
 * 三路快速排序 针对大量重复元素
 */
public class QuickSortV5 {
    private QuickSortV5() {

    }

    public static <E extends  Comparable<E>> void sort(E[] arr) {
        Random rnd = new Random();
        sort(arr,0,arr.length-1,rnd);
    }

    private static <E extends  Comparable<E>> void sort(E[] arr, int l, int r, Random rnd) {
        if (l>=r) return;

        // 生成[l,r] 之间的随机索引
        int p = l+rnd.nextInt(r-l+1);
        swap(arr,l,p);

        // arr[l+1...lt] < v,arr[lt+1...i-1] == v arr[gt...r] > v
        int lt = l,i=l+1,gt=r+1;
        while (i<gt) {
            if (arr[i].compareTo(arr[l])<0) {
                lt++;
                swap(arr,i,lt);
                i++;
            }else if (arr[i].compareTo(arr[l])>0) {
                gt--;
                swap(arr,i,gt);
            }else { // arr[i] == arr[l]
                i++;
            }
        }
        swap(arr,l,lt);
        // arr[l,lt-1] < v,arr[lt,gt-1] == v arr[gt,r] > v
        sort(arr,l,lt-1,rnd);
        sort(arr,gt,r,rnd);
    }

    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr[i];
        arr[i] =arr[j];
        arr[j] =t;
    }

    public static void main(String[] args) {
        int n = 1000000;
        System.out.println("RandomArray");
        Integer[] arr =ArrayGenerator.generateRandomArray(n,n);
        Integer[] arr4_3 = Arrays.copyOf(arr,arr.length);
        Integer[] arr4_4 = Arrays.copyOf(arr,arr.length);
        SortingHelper.sortTest("QuickSortV3",arr4_3);
        SortingHelper.sortTest("QuickSortV4",arr4_4);
        SortingHelper.sortTest("QuickSortV5",arr);

        System.out.println("OrderedArray");
        Integer[] arr5 =ArrayGenerator.generateOrderedArray(n);
        Integer[] arr6 = Arrays.copyOf(arr5,arr.length);
        Integer[] arr6_1 = Arrays.copyOf(arr5,arr.length);
        SortingHelper.sortTest("QuickSortV4",arr6);
        SortingHelper.sortTest("QuickSortV3",arr5);
        SortingHelper.sortTest("QuickSortV5",arr6_1);


        System.out.println("SameValueArray");
        Integer[] arr1_3 =ArrayGenerator.generateRandomArray(n,1);
        Integer[] arr1_3_2 = Arrays.copyOf(arr1_3,arr.length);
        SortingHelper.sortTest("QuickSortV4",arr1_3);
        // SortingHelper.sortTest("QuickSortV3",arr1_3_2); // StackOverflowError
        SortingHelper.sortTest("QuickSortV5",arr1_3_2);
    }
}
